import org.junit.jupiter.api.Test;

/**
 * @author ZhengDp
 * @Date 2023/5/3 16:35
 */
public class 图论算法 {

    @Test
    void dijkstraTest(){
        char[] vertices = new char[]{'A','B','C','D'};
        int[][] graph = new int[][]{
                {0, 2, -1, 6}
                , {2, 0, 3, 2}
                , {-1, 3, 0, 2}
                , {6, 2, 2, 0}};
        int[] dijkstra = dijkstra(graph, 0);
        for (int i : dijkstra) {
            System.out.println(i);
        }
    }

    // Dijkstra算法 ==> 求一个点到其他所有点的最短距离
    private int[] dijkstra(int[][] graph,int start){
        int length = graph.length;
        // result[i] ==> 顶点i 到 start的最小路径
        int[] result = new int[length];
        for(int i =0;i<length;i++) {
            result[i] = -1;
        }
        result[start] = 0;
        // notFound[i] : i到start的路径 （未加入到最小路径中的顶点）
        int[] notFound = new int[length];
        for(int i=0;i<length;i++) {
            notFound[i] = graph[start][i];
        }
        // 表示当前结点已经加入到最小路径中
        notFound[start] = -1;
        for(int i =1;i<length;i++) {
            // 1. 从 notFound找到最短路径的点
            int min = Integer.MAX_VALUE;
            int minIndex = 0;
            for(int j =0;j<length;j++) {
                if(notFound[j] > 0 && notFound[j] < min) {
                    min = notFound[j];
                    minIndex=j;
                }
            }
            // 2. 将最短路径的点取出，放入到结果集中
            result[minIndex] = min;
            notFound[minIndex] =-1;
            // 3. 更新 notFound中的距离
            for(int j =0;j<length;j++) {
                // 找到当前加入的顶点的出度，更新其与顶点之间的距离
                // result[j] == -1 :需要更新的是没有在结果集中的出度点
                if(graph[minIndex][j] > 0 && result[j] == -1) {
                    int newDistance = result[minIndex] + graph[minIndex][j];
                    if(newDistance < notFound[j] || notFound[j] == -1) {
                        notFound[j] = newDistance;
                    }
                }
            }
        }
        return result;
    }
}
